//
//  Vector_deduplicate.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/5.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension Vector where Element: Equatable {
    /// 无序向量去重
    public func deduplicate() -> Int {
        if _size <= 1 { return 0 }
        let oldSize = _size
        // 主体思想是将vector分为两部分 已去重的和待去重的
        // 每次从待去重的区间里取一个元素 如果在已去重的区间内命中 就删除这个元素
        // 直到遍历完整个vector
        var undoStartIndex = startIndex + 1
        while undoStartIndex < endIndex {
            let hitIndex = find(_storage[undoStartIndex], at: startIndex..<undoStartIndex)
            if hitIndex != NotFound {
                // 隐式减小_size
                // 从待去重区间中删除重复元素
                // 可以保证元素的相对位置不变
                remove(at: undoStartIndex)
            } else {
                undoStartIndex += 1
            }
        }
        return oldSize - _size
    }
}
